#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/30 11:28
# @USER    : Shengji He
# @File    : IntegerBreak.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def integerBreak(self, n: int) -> int:
        """
        Given a positive integer n, break it into the sum of at least two positive integers and maximize the
        product of those integers. Return the maximum product you can get.

        Example 1:
            Input: 2

            Output: 1

            Explanation: 2 = 1 + 1, 1 × 1 = 1.
        Example 2:
            Input: 10

            Output: 36

            Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
        Note: You may assume that n is not less than 2 and not larger than 58.

        :param n:
        :return:
        """
        if n <= 3:
            return n - 1

        quotient, remainder = divmod(n, 3)
        if remainder == 0:
            return 3 ** quotient
        elif remainder == 1:
            return 3 ** (quotient - 1) * 4
        else:
            return 3 ** quotient * 2


if __name__ == '__main__':
    S = Solution()
    n = 10
    print(S.integerBreak(n))
    print('done')
